package xin.javashare.sort;

/**
 * 程序清单24.9 【堆排序】
 * 时间复杂度O(nlogn),
 * 不需要额外的数组空间，空间效率高于归并排序
 */
public class HeapSort {
    public static <E extends Comparable> void heapSort(E[] list) {
        Heap<E> heap = new Heap<E>();

        for (int i = 0; i < list.length; i++) {
            heap.add(list[i]);
        }

        for (int i = list.length - 1; i >= 0; i--) {
            list[i] = heap.remove();
        }
    }

    public static void main(String[] args) {
        Integer[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        heapSort(list);

        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
}
